package com.atguigu.algorithm;
//class TreeNode {
//      int val;
//      TreeNode left;
//      TreeNode right;
//      TreeNode() {}
//      TreeNode(int val) { this.val = val; }
//      TreeNode(int val, TreeNode left, TreeNode right) {
//          this.val = val;
//         this.left = left;
//          this.right = right;
//      }
//  }
public class UseInPreToFromTree {
    public static void main(String[] args) {
        int[] preorder=new int[]{3,9,20,15,7};
        int[] inorder=new int[]{9,3,15,20,7};
        UseInPreToFromTree us=new UseInPreToFromTree();
        us.buildTree(preorder,inorder);
        System.out.println(us);
    }
    int index=0;
    public TreeNode buildTree(int[] preorder,int[] inorder){
        return buildTree(preorder,inorder,0,inorder.length);
    }
    public TreeNode buildTree(int[] preorder,int[] inorder,int left,int right){
        if(left >= right){
            return null;
        }
        // 创建跟节点
        TreeNode root = new TreeNode(preorder[index]);
        // 在中序遍历结果中找到根的位置
        int rootIdx = left;
        while(rootIdx < right){
            if(inorder[rootIdx] == preorder[index])
                break;

            rootIdx++;
        }
        index++;
        //[left, rootIdx)：左子树中的所有节点
        // 递归创建根的左子树
        root.left = buildTree(preorder, inorder, left, rootIdx);
        //[rootIdx+1, right): 右子树中的所有节点
        // 递归创建根的右子树
        root.right = buildTree(preorder, inorder, rootIdx+1, right);
        return root;
    }
}
